//
// Created by 顿 on 2022/10/17 0017.
//
#include <vector>
#include <queue>
using namespace std;
template<class W>
struct HuffmanTreeNode{
    HuffmanTreeNode<W>* _left;
    HuffmanTreeNode<W>* _right;
    HuffmanTreeNode<W>* _parent;
    W _weight;
    HuffmanTreeNode(const W& weight=W()):
    _weight(weight),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

template<class W>
class  HuffmanTree{
    typedef HuffmanTreeNode<W> Node;
    class Compare{
    public:
        bool operator()(Node* left,Node* right){return left->_weight>right->_weight;}
    };
public:
    HuffmanTree():_root(nullptr){}
    //1．用所有的权值构造只有根节点的二叉树森林
    // 森林中二叉树应该使用堆(优先级队列)来保存
    HuffmanTree(const vector<W>&vw, const W& invalid){
        //默认小堆，使用大堆
        priority_queue<Node*,vector<Node*>,Compare> q;
        for(auto& e:vw){
            if(invalid!=e)
                q.push(new Node(e));
        }
        while(q.size()>1){
            Node* left=q.top();
            q.pop();
            Node* right=q.top();
            q.pop();
            Node* parent=new Node(left->_weight+right->_weight);
            parent->_left=left;
            parent->_right=right;
            left->_parent=parent;
            right->_parent=parent;
            q.push(parent);
        }
        _root=q.top();

    }
    ~HuffmanTree(){
        Destroy(_root);
    }
    Node* GetRoot(){
        return _root;
    }
private:
    void Destroy(Node*& root){
        if(root!= nullptr){
            Destroy(root->_left);
            Destroy(root->_right);
            delete root;
            root= nullptr;
        }
    }
    Node *_root;
};

/*
void test(){
    vector<int>v{7,5,3,1};
    HuffmanTree<int>ht(v);
}*/
